package com.maozzi.dp;

import java.util.Arrays;

/**
 * 背包问题
 * 1. 01背包
 * 2. 完全背包
 *
 * @author maozi
 */
public class Bag {
    public static void main(String[] args) {
        System.out.println(bag2D());
        System.out.println(bag1D());
    }

    /**
     * 01背包问题
     * <p>
     * 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。
     * 每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
     * <p>
     * 背包最大重量为4。
     * 物品为：
     * 物品   重量  价值
     * 物品0  1   15
     * 物品1  3   20
     * 物品2  4   30
     * 问背包能背的物品最大价值是多少？
     * <p>
     * 二维数组解法
     */
    public static int bag2D() {
        // dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int capacity = 4;
        int[][] dp = new int[weight.length][capacity + 1];
        for (int i = 0; i <= capacity; i++) {
            dp[0][i] = value[0];
        }
        for (int i = 0; i < weight.length; i++) {
            dp[i][0] = 0;
        }
        // 先遍历物品，再遍历背包容量
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j >= weight[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(Arrays.deepToString(dp));
        return dp[2][4];
    }

    /**
     * 01背包，一维数组
     */
    public static int bag1D() {
        // dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int capacity = 4;
        int[] dp = new int[capacity + 1];
        // 先遍历物品，再遍历背包容量
        for (int i = 0; i < weight.length; i++) {
            // 倒序，为了前一个dp[i-1]没有反复加
            for (int j = capacity; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[capacity];
    }

    /**
     * 完全背包问题
     * <p>
     * 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。
     * 每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
     * <p>
     * 一维数组解法
     */
    public static int completeBag() {
        // dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int capacity = 4;
        int[] dp = new int[capacity + 1];
        // 在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的
        for (int i = 0; i < weight.length; i++) {
            for (int j = weight[i]; j <= capacity; j++) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[capacity];
    }

}
